package leetcode.题库.数组.普通数组;

/**
 * 下一个排列
 *
 * @author yanzhenming
 * @date 2023/3/23  19:10
 */

/**
 * 描述
 *
 * 下一个最大的排列，如123，下一个是132
 */

import java.util.Arrays;

/**
 * 思路
 *
 * 找到逆序点，交换
 * 逆序点  0之后逆序
 */
public class Solution31 {

    public static void main(String[] args) {
        int[] arr = new int[]{3,2,1};
        nextPermutation(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void nextPermutation(int[] nums) {
        int reversePoint = -1;
        // 找到逆序点
        for (int i = nums.length - 1; i > 0; i--){
            if (nums[i-1] < nums[i]) {
                reversePoint = i-1;
                break;
            }
        }
        if(reversePoint != -1) {
            // 找到第一个比逆序点大的值，进行交换
            for (int i = nums.length - 1; i >= 0; i--){
                if (nums[reversePoint] < nums[i]) {
                    int temp = nums[reversePoint];
                    nums[reversePoint] = nums[i];
                    nums[i] = temp;
                    break;
                }
            }
        }

        // 逆序操作
        reverse(nums, reversePoint+1, nums.length - 1);
    }

    public static void reverse(int[] nums, int left, int right){
        while(left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;right--;
        }
    }

//    public static void nextPermutation(int[] nums) {
//        // 从后往前找到第一个逆序点
//        int reservePoint = -1;
//        for (int i = nums.length-1; i > 0; i--) {
//            if (nums[i] > nums[i-1]) {
//                reservePoint = i-1;
//                break;
//            }
//        }
//        if (reservePoint != -1) {
//            for(int i = nums.length-1; i >= 0; i--) {
//                if (nums[i] > nums[reservePoint]){
//                    int temp = nums[i];
//                    nums[i] = nums[reservePoint];
//                    nums[reservePoint] = temp;
//                    break;
//                }
//            }
//        }
//        reserve(nums, reservePoint+1, nums.length-1);
//    }
//
//    public static void reserve(int[] nums, int start, int end) {
//        while (start < end) {
//            int temp = nums[start];
//            nums[start] = nums[end];
//            nums[end] = temp;
//            start++;
//            end--;
//        }
//    }
}
